package org.example.BinaryTree;

import java.util.ArrayList;

public class Delete_nodes_in_binary_search_tree {
    public static ArrayList<TreeNode> list = new ArrayList<>();
    public static TreeNode node = null;
    public static boolean flag = false;
    public static void main(String[] args) {
        //删除二叉搜索树中的节点

        //给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
        //一般来说，删除节点可分为两个步骤：
        //首先找到需要删除的节点；
        //如果找到了，删除它。
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(10);
        TreeNode root = new TreeNode(3);
        TreeNode node5 = new TreeNode(8);
        TreeNode node6 = new TreeNode(15);
        TreeNode node7 = new TreeNode(7);
        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        node4.left = node5;
        node4.right = node6;
        node5.left = node7;
        TreeNode treeNode = deleteNode(root, 7);
        search(treeNode);
    }

    public static TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val==key){
            if (root.left==null) return root.right;
            if (root.right==null) return root.left;
            insert(root.left,root.right);
            return root.left;
        }
        //删除节点
        removeNode(root, key);
        //重构搜索二叉树
        return insertNode(root);
    }

    public static void removeNode(TreeNode root, int key) {
        if (root == null || flag) return;
        if (root.left!=null && root.left.val==key) {
            node = root;
            if (root.left.left != null) list.add(root.left.left);
            if (root.left.right != null) list.add(root.left.right);
            root.left.left = null;
            root.left.right = null;
            root.left = null;
            flag = true;
            return;
        }
        if (root.right!=null && root.right.val==key) {
            node = root;
            if (root.right.left != null) list.add(root.right.left);
            if (root.right.right != null) list.add(root.right.right);
            root.right.left = null;
            root.right.right = null;
            root.right = null;
            flag = true;
            return;
        }
        removeNode(root.left, key);
        removeNode(root.right, key);
    }

    public static TreeNode insertNode(TreeNode root) {
        if (!flag) return root;
        switch (list.size()){
            case 1:
                if (node.val>list.get(0).val) node.left = list.get(0);
                if (node.val<list.get(0).val) node.right = list.get(0);
                break;
            case 2:
                insert(list.get(0),list.get(1));
                if (node.val>list.get(0).val) node.left = list.get(0);
                if (node.val<list.get(0).val) node.right = list.get(0);
                break;
        }
        return root;
    }
    public static void insert(TreeNode node, TreeNode in){
        if (in.val<node.val&&node.left==null){
            node.left = in;
        }else if (in.val>node.val&&node.right==null){
            node.right = in;
        }else if (in.val<node.val){
            insert(node.left,in);
        }else {
            insert(node.right,in);
        }
    }
    public static void search(TreeNode root){
        if (root==null) return;
        System.out.print(root.val+" ");
        search(root.left);
        search(root.right);
    }

    //别人的方法，真简洁，真牛逼，我感觉我写的就是一堆屎
    public TreeNode deleteNode2(TreeNode root, int key) {
        if (root == null) return root;
        if (root.val == key) {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                //完美的实现了父节点和子节点的连接，将目标节点轻松删除
                TreeNode cur = root.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;
                return root;
            }
        }
        if (root.val > key) root.left = deleteNode2(root.left, key);
        if (root.val < key) root.right = deleteNode2(root.right, key);
        return root;
    }
}
